/**
 * 设计一个 map ，满足以下几点:
 *
 * 字符串表示键，整数表示值
 * 返回具有前缀等于给定字符串的键的值的总和
 * 实现一个 MapSum 类：
 *
 * MapSum() 初始化 MapSum 对象
 * void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。
 * int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
 *
 * 链接：https://leetcode.cn/problems/map-sum-pairs
 * 
 */
class MapSum {
    private static class TrieNode {
        TrieNode[] children=new TrieNode[26];
        int val=0;
    }
    private TrieNode root;
    public MapSum() {
        root=new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode p=root;
        int len=key.length();
        for(int i=0;i<len;i++) {
            char c=key.charAt(i);
            if(p.children[c-'a']==null) {
                p.children[c-'a']=new TrieNode();
            }
            p=p.children[c-'a'];
        }
        p.val=val;
    }
    private TrieNode getNode(TrieNode node,String prefix) {
        int len=prefix.length();
        for(int i=0;i<len;i++) {
            if(node==null) {
                return null;
            }
            char c=prefix.charAt(i);
           node=node.children[c-'a'];
        }
        return node;
    }
    public int sum(String prefix) {
        TrieNode p=getNode(root,prefix);
        if(p==null) {
            return 0;
        }
       return travel(p);
    }
    private int travel(TrieNode p) {
        if(p==null) {
            return 0;
        }
        int sum=0;
        for(int i=0;i<26;i++) {
           sum+=travel(p.children[i]);
        }
        return sum+p.val;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */